package offer2

/**
https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=265

B站 吴师兄学算法
剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:
3
/ \
4   5
/ \
1   2

给定的树 B：
4
/
1
*/

func isSubStructure(A *TreeNode, B *TreeNode) bool {
	if A == nil || B == nil {
		return false
	}

	return isSub(A, B) || isSubStructure(A.Left, B) || isSubStructure(A.Right, B)
}

func isSub(A *TreeNode, B *TreeNode) bool {
	if B == nil { //b已经没有节点了, 直接返回true即可
		return true
	}
	if A == nil || A.Val != B.Val { //a已经没有节点了, 或者A和B的值不相等了, 直接返回false即可
		return false
	}

	//如果当前轮节点满足条件, 那么递归比较a,b的左节点 a,b的右节点
	return isSub(A.Left, B.Left) && isSub(A.Right, B.Right)
}
